from typing import List

"""
分行 分列 分块的暴力算法
"""


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            res = []
            res2 = []
            for j in range(9):
                if board[i][j] != ".":
                    if board[i][j] in res:
                        return False
                    else:
                        res.append(board[i][j])
                if board[j][i] != ".":
                    if board[j][i] in res2:
                        return False
                    else:
                        res2.append(board[j][i])
        for i in [0, 3, 6]:
            for j in [0, 3, 6]:
                res = []
                for k in range(3):
                    for l in range(3):
                        if board[i + k][j + l] != ".":
                            if board[i + k][j + l] in res:
                                return False
                            else:
                                res.append(board[i + k][j + l])

        return True
    #哈希表改造
    def isValidSudoku2(self, board: List[List[str]]) -> bool:
        # 初始化哈希表
        rows = [{} for _ in range(9)]
        cols = [{} for _ in range(9)]
        boxes = [{} for _ in range(9)]

        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != ".":
                    # 计算子网格的索引
                    box_index = (i // 3) * 3 + j // 3

                    # 检查行、列和子网格中是否有重复值
                    if num in rows[i] or num in cols[j] or num in boxes[box_index]:
                        return False

                    # 将值添加到哈希表中
                    rows[i][num] = 1
                    cols[j][num] = 1
                    boxes[box_index][num] = 1

        return True








braod = [["5", "3", ".", ".", "7", ".", ".", ".", "."]
    , ["6", ".", ".", "1", "9", "5", ".", ".", "."]
    , [".", "9", "8", ".", ".", ".", ".", "6", "."]
    , ["8", ".", ".", ".", "6", ".", ".", ".", "3"]
    , ["4", ".", ".", "8", ".", "3", ".", ".", "1"]
    , ["7", ".", ".", ".", "2", ".", ".", ".", "6"]
    , [".", "6", ".", ".", ".", ".", "2", "8", "."]
    , [".", ".", ".", "4", "1", "9", ".", ".", "5"]
    , [".", ".", ".", ".", "8", ".", ".", "7", "9"]]

lll = Solution()
print(lll.isValidSudoku(braod))
